package com.ly.algorithm.DataStructures.problem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Classname Prim
 * @Description TODO
 * @Date 2020/5/4 17:44
 * @Author 冷心影翼
 */
public class Prim {

    public static void main(String[] args) {
        int verxs = 7;
        char[] data = {'A','B','C','D','E','F','G'};
        Graph graph = new Graph(verxs,data);
        graph.insertVerxs(0,1,5);
        graph.insertVerxs(0,2,7);
        graph.insertVerxs(0,6,2);
        graph.insertVerxs(1,3,9);
        graph.insertVerxs(1,6,3);
        graph.insertVerxs(2,3,8);
        graph.insertVerxs(3,5,4);
        graph.insertVerxs(4,5,5);
        graph.insertVerxs(4,6,4);
        graph.insertVerxs(4,5,5);
        graph.insertVerxs(5,6,6);
        graph.showGraph();
        graph.prim(1);
    }
}

class Graph{
    private int[][] weight;

    private int verxs;

    private char[] data;

    private List<Integer> res;

    private int value;

    public Graph(int verxs, char[] data) {
        this.weight = new int[verxs][verxs];
        this.verxs = verxs;
        this.data = data;
        res = new ArrayList<>();
    }

    public void insertVerxs(int i,int j,int w) {
        weight[i][j] = w;
        weight[j][i] = w;
    }

    public void showGraph() {
        for(int[] r:weight) {
            System.out.println(Arrays.toString(r));
        }
    }

    public void prim(int v) {
        res.add(v);
        for(int k=1;k<verxs;k++) {
            int min = 0;
            int v1 = 0;
            int v2 = 0;
            for (int it : res) {
                for(int i=0;i<verxs;i++) {
                    if(weight[it][i]==0) {
                        continue;
                    }
                    if( !res.contains(i) && (min>weight[it][i] || min == 0)) {
                        min = weight[it][i];
                        v1 = it;
                        v2 = i;
                    }
                }
            }
            res.add(v2);
            value+=min;
            System.out.println(v1+"->"+v2 +" "+ min);
        }
        System.out.println(value);
    }
}
